A Modified PRP Conjugate Gradient Algorithm with Trust Region for Optimization Problems

In this article, a modified PRP algorithm is presented for unconstrained optimization problems. This method possesses sufficiently descent property and the proposed direction is in a trust region. The global convergence and the linear convergence rate of the given method are established under weaker conditions. Numerical results show that the presented method is effective.     

Heuristic algorithms for the cardinality constrained efficient frontier

This paper examines the application of genetic algorithm, tabu search and simulated annealing metaheuristic approaches to finding the cardinality constrained efficient frontier that arises in financial portfolio optimisation. We consider the mean-variance model of Markowitz as extended to include the discrete restrictions of buy-in thresholds and cardinality constraints. Computational results are reported for publicly available data sets drawn from seven major market indices involving up to 1318 assets. Our results are compared with previous results given in the literature illustrating the effectiveness of the proposed metaheuristics in terms of solution quality and computation time.     

Local search and suffix tree for car-sequencing problem with colors

This paper describes an approximation solution method for the car sequencing problem with colors. Firstly, we study the optimality of problems with a single ratio constraint. This study also introduces a data structure for efficient calculation of the penalties related to ratio constraints. We describe the constructive greedy algorithm and variable neighborhood search adjusted for the problem with colors. Tabu metaheuristic is used to improve the results obtained by VNS. We then represent the cars with their constraints as letters over an alphabet and apply the algorithm to spell the motifs in order to improve the number of batch colors without decreasing the costs associated to the set of ratio constraints. The algorithm achieves 19 out of the 64 best results for instance sets A and B. These instances are the reference instances for Challenge ROADEF.     

Weighted search games

In this paper we shall deal with search games in which the strategic situation is developed on a lattice. The main characteristic of these games is that the points in each column of the lattice have a specific associated weight which directly affects the payoff function. Thus, the points in different columns represent points of different strategic value. We solve three different types of games. The first involves search, ambush and mixed situations, the second is a search and inspection game and the last is related to the accumulative games.     

Discounted MEAN bound for the optimal searcher path problem with non-uniform travel times

We consider an extension of the optimal searcher path problem (OSP), where a searcher moving through a discretised environment may now need to spend a non-uniform amount of time travelling from one region to another before being able to search it for the presence of a moving target. In constraining not only where but when the search of each cell can take place, the problem more appropriately models the search of environments which cannot be easily partitioned into equally sized cells. An existing OSP bounding method in literature, the MEAN bound, is generalised to provide bounds for solving the new problem in a branch and bound framework. The main contribution of this paper is an enhancement, discounted MEAN (DMEAN), which greatly tightens the bound for the new and existing problems alike with almost no additional computation. We test the new algorithm against existing OSP bounding methods and show it leads to faster solution times for moving target search problems.     

A tabu search and a genetic algorithm for solving a bicriteria general job shop scheduling problem

This paper deals with a general job shop scheduling problem with multiple constraints, coming from printing and boarding industry. The objective is the minimization of two criteria, the makespan and the maximum lateness, and we are interested in finding an approximation of the Pareto frontier. We propose a fast and elitist genetic algorithm based on NSGA-II for solving the problem. The initial population of this algorithm is either randomly generated or partially generated by using a tabu search algorithm, that minimizes a linear combination of the two criteria. Both the genetic and the tabu search algorithms are tested on benchmark instances from flexible job shop literature and computational results show the interest of both methods to obtain an efficient and effective resolution method.     

A tabu search heuristic for the generalized minimum spanning tree problem

This paper describes an attribute based tabu search heuristic for the generalized minimum spanning tree problem (GMSTP) known to be NP-hard. Given a graph whose vertex set is partitioned into clusters, the GMSTP consists of designing a minimum cost tree spanning all clusters. An attribute based tabu search heuristic employing new neighborhoods is proposed. An extended set of TSPLIB test instances for the GMSTP is generated and the heuristic is compared with recently proposed genetic algorithms. The proposed heuristic yields the best results for all instances. Moreover, an adaptation of the tabu search algorithm is proposed for a variation of the GMSTP in which each cluster must be spanned at least once.     

A Clustering Search metaheuristic for the Point-Feature Cartographic Label Placement Problem

The Point-Feature Cartographic Label Placement (PFCLP) problem consists of placing text labels to point features on a map avoiding overlaps to improve map visualization. This paper presents a Clustering Search (CS) metaheuristic as a new alternative to solve the PFCLP problem. Computational experiments were performed over sets of instances with up to 13,206 points. These instances are the same used in several recent and important researches about the PFCLP problem. The results enhance the potential of CS by finding optimal solutions (proven in previous works) and improving the best-known solutions for instances whose optimal solutions are unknown so far.     

A heuristic for scheduling in a two-stage hybrid flowshop with renewable resources shared among the stages

In this paper we propose a heuristic for solving the problem of resource constrained preemptive scheduling in the two-stage flowshop with one machine at the first stage and parallel unrelated machines at the second stage, where renewable resources are shared among the stages, so some quantities of the same resource can be used at different stages at the same time. Availability of every resource at any moment is limited and resource requirements of jobs are arbitrary. The objective is minimization of makespan. The problem is NP-hard. The heuristic first sequences jobs on the machine at stage 1 and then solves the preemptive scheduling problem at stage 2. Priority rules which depend on processing times and resource requirements of jobs are proposed for sequencing jobs at stage 1. A column generation algorithm which involves linear programming, a tabu search algorithm and a greedy procedure is proposed to minimize the makespan at stage 2. A lower bound on the optimal makespan in which sharing of the resources between the stages is taken into account is also derived. The performance of the heuristic evaluated experimentally by comparing the solutions to the lower bound is satisfactory.